package com.aynu.linkedList;

import java.util.Stack;

public class SignleLinkedListTest {
	public static void main(String[] args) {
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		HerNode herNode1 = new HerNode(1, "宋江", "及时雨");
		HerNode herNode2 = new HerNode(2, "卢俊义", "玉麒麟");
		HerNode herNode3 = new HerNode(3, "吴用", "智多星");
		HerNode herNode4 = new HerNode(4, "林冲", "豹子头");

		SingleLinkedList singleLinkedList2 = new SingleLinkedList();
		HerNode herNode5 = new HerNode(5, "宋江", "及时雨");
		HerNode herNode6 = new HerNode(6, "卢俊义", "玉麒麟");
		HerNode herNode7 = new HerNode(7, "吴用", "智多星");
		HerNode herNode8 = new HerNode(8, "林冲", "豹子头");

		// 添加
		singleLinkedList.addByOrder(herNode4);
		singleLinkedList.addByOrder(herNode3);
		singleLinkedList.addByOrder(herNode2);
		singleLinkedList.addByOrder(herNode1);

		singleLinkedList2.addByOrder(herNode5);
		singleLinkedList2.addByOrder(herNode6);
		singleLinkedList2.addByOrder(herNode7);
		singleLinkedList2.addByOrder(herNode8);

		// 两个有序链表实现合并
		heBing(singleLinkedList.getHead(), singleLinkedList2.getHead());

		singleLinkedList.list();

//		singleLinkedList.addByOrder(herNode3);
//		singleLinkedList.addByOrder(herNode3);

		// 修改
//		singleLinkedList.update(new HerNode(2, "张三", "NB"));

		// 删除
//		singleLinkedList.delete(1);
//		singleLinkedList.delete(2);
//		singleLinkedList.delete(3);
//		singleLinkedList.delete(4);

//		singleLinkedList.addByOrder(herNode1);
//		singleLinkedList.addByOrder(herNode4);

		System.out.println("反转。。。。");
//		System.out.println("反转");
		reverseLinkedList(singleLinkedList.getHead());

		// 反向打印
		//reversePrint(singleLinkedList.getHead());

		// 打印
		singleLinkedList.list();

		// 有效数据个数
		//System.out.println(getLength(singleLinkedList.getHead()));

		// 倒数index个的节点
		//System.out.println(findLastIndexNode(singleLinkedList.getHead(), 3));
	}

	public static void heBing(HerNode head1, HerNode head2) {

		if (head1.next == null || head2.next == null) {
			return;
		}

		HerNode temp1 = head1.next;
		HerNode temp2 = head2.next;
		HerNode newNode = new HerNode(0, "", "");
		HerNode temp3 = newNode;
		HerNode next = null;

		// head1插入到newNode
		while (temp1 != null) {
			next = temp1.next;

			boolean flag = false;

			while (temp3.next != null) {
				if (temp3.next.no > temp1.no) {
					return;
				} else if (temp3.next.no == temp1.no) {
					flag = true;
					break;
				}
				temp3 = temp3.next;
			}

			if (flag) {
				System.out.printf("相同的编号  %d 不同插入", temp1.no);
			} else {
				temp1.next = temp3.next;
				temp3.next = temp1;
			}

			temp1 = next;
		}

		while (temp2 != null) {
			next = temp2.next;

			boolean flag = false;

			while (temp3.next != null) {
				if (temp3.next.no > temp2.no) {
					break;
				} else if (temp3.next.no == temp2.no) {
					flag = false;
					break;
				}
				temp3 = temp3.next;
			}
			if (flag) {
				System.out.printf("相同的编号  %d 不同插入", temp1.no);
			} else {
				temp2.next = temp3.next;
				temp3.next = temp2;
			}

			temp2 = next;
		}

		head1.next = newNode.next;
	}

	/**
	 * 获取单链表的节点数（把头节点排除在外）
	 * 
	 * @param head 链表的头节点
	 * @return 返回链表的有效个数
	 */
	public static int getLength(HerNode head) {
		if (head.next == null) {
			return 0;
		}

		int length = 0;
		HerNode curentNode = head.next;
		while (curentNode != null) {
			length++;
			curentNode = curentNode.next;
		}
		return length;
	}

	// 查找单链表的倒数第k个节点
	// 思路：
	// 1. 编写一个方法，接收head节点，同时接收一个index
	// 2. index表示：倒数第index个节点
	// 3. 先把链表从头到尾遍历一遍，得到链表的总长度getLength
	// 4. 得到size后，我们从链表的第一个开始遍历（size-index）个
	// 5. 如果找到了，則放回該节点，否则返回null
	public static HerNode findLastIndexNode(HerNode head, int index) {
		// 判断链表为空，返回null
		if (head.next == null) {
			return null;
		}

		// 定义辅助变量
		HerNode cur = head.next;
		int size = getLength(head);

		// 判断index是否非法
		if (index <= 0 || index > size) {
			return null;
		}

		// 使用for循环来完成节点的查找
		for (int i = 0; i < size - index; i++) {
			cur = cur.next;
		}

		return cur;
	}

	// 利用栈这个数据结构，将各个点压入栈中，然后利用栈先进先出的特点，实现逆序打印的效果
	public static void reversePrint(HerNode head) {
		// 判断是否为空
		if (head.next == null) {
			return;
		}

		// 创建辅助节点cur
		HerNode cur = head.next;
		// 创建栈
		Stack<HerNode> stack = new Stack<HerNode>();
		// 循环存入stack中
		while (cur != null) {
			stack.push(cur);
			cur = cur.next;
		}
		// 循环打印数据
		while (stack.size() > 0) {
			System.out.println(stack.pop());
		}

	}

	// 链表反转【腾讯面试题】
	public static void reverseLinkedList(HerNode head) {
		// 如果链表为空，或只有一个节点，无需反转，直接返回
		if (head.next == null || head.next.next == null) {
			return;
		}

		// 定义一个辅助变量，帮组我们遍历原来的链表
		HerNode cur = head.next;
		HerNode temp = null;// 用来循环的链表的关键过度节点，指向当前节点下一个节点
		HerNode reseverNode = new HerNode(0, "", "");// 新的一个链表头

		// 遍历原来的链表，每遍历一个节点，就将其取出，并放到新的链表reseverNode的最前端
		while (cur != null) {
			// 暂时保存当前节点的下一个节点，后面需要用
			temp = cur.next;
			// 存进新的数组
			cur.next = reseverNode.next;// 将当前的最前端节点，往后移
			reseverNode.next = cur;// 设置最前端节点
			cur = temp;// 让cur往后移
		}

		// 将head.next指向reseverNode.next，实现单链表的反转
		head.next = reseverNode.next;
	}
}

//定义一个SingleLinkedList，来管理HerNode,不考虑英雄的编号，直接插入到尾部
class SingleLinkedList {
	// 首先初始化一个头节点，不存放具体数据
	private HerNode head = new HerNode(0, "", "");

	public HerNode getHead() {
		return head;
	}

	// 添加节点到单向链表
	// 思路：当不考录编号的顺序时
	// 1. 找到尾节点
	// 2. 将最后节点的next，指向新节点
	@SuppressWarnings("unused")
	private void add(HerNode herNode) {
		// 因为head节点不能动，因此我们需要一个辅助遍历节点-temp
		HerNode temp = head;
		while (true) {
			// 找到链表的最后
			if (temp.next == null) {
				break;
			}
			// 如果没有找到，就将链表后移
			temp = temp.next;
		}
		// 当退出while循环时，temp指向最后的节点
		temp.next = herNode;
	}

	// 第二种方式，根据英雄的排名，将英雄节点插入到指定位置
	// 如果有这个排名，则添加失败，并给出提示
	public void addByOrder(HerNode herNode) {
		// 因为头节点不能动，所以需要一个辅助变量，来完成遍历
		HerNode temp = head;
		// 标志位，是否存在排名的节点？插入失败 ：插入成功
		boolean flag = false;
		while (true) {
			// 遍历到链表的结尾，退出循环
			if (temp.next == null) {
				break;
			}
			// 位置找到，就在temp后面插入
			if (temp.next.no > herNode.no) {
				break;
			} else if (temp.next.no == herNode.no) {// 说明需要添加的节点的排名已存在
				flag = true;
				break;
			}
			temp = temp.next;
		}
		// 判断flag的值
		if (flag) {// 不能添加，说明编号以存在
			System.out.printf("添加的英雄的节点 %d 已存在，不能加入\n", herNode.no);
		} else {
			// 添加到链表中，temp后面
			herNode.next = temp.next;
			temp.next = herNode;
		}
	}

	// 修改节点：根据newHeroNode的no进行修改
	public void update(HerNode newHerNode) {
		// 判断是否为空
		if (head.next == null) {
			System.out.println("链表为空");
			return;
		}
		// 定义一个辅助变量
		HerNode temp = head.next;
		boolean flag = false;// 表示是否找到节点
		while (temp != null) {
			// 找到需要修改的节点
			if (temp.no == newHerNode.no) {
				flag = true;
				break;
			}
			// 遍历
			temp = temp.next;
		}

		// 根据flag，判断是否找到修改的节点
		if (flag) {
			temp.name = newHerNode.name;
			temp.nickName = newHerNode.nickName;
		} else {// 没有找到
			System.out.printf("没有找到编号 %d 的节点，不能修改\n", newHerNode.no);
		}
	}

	// 删除节点
	// 思路：
	// 1. head不能动，所以需要一个辅助节点，来完成遍历，找到待删除节点的前一个节点
	// 2. 在比较时，比较temp.next.no == 需要删除节点的no ??
	public void delete(int no) {
		// 判断链表是否为空
		if (head.next == null) {
			System.out.println("链表为空");
			return;
		}

		HerNode temp = head;// 创建一个辅助变量
		boolean flag = false;// 标志位，是否找到待删除的节点
		while (temp.next != null) {
			if (temp.next.no == no) {
				// 找到删除节点的前一个节点
				flag = true;
				break;
			}
			temp = temp.next;
		}
		// 判断flag
		if (flag) {// 存在
			temp.next = temp.next.next;
		} else {
			System.out.printf("没有找到节点 %d ，因为该节点不存在\n", no);
		}
	}

	// 遍历链表
	public void list() {
		HerNode temp = head.next;

		if (temp == null) {
			System.out.println("链表为空");
			return;
		}

		while (temp != null) {
			// 输出节点信息
			System.out.println(temp);
			// temp，往后移
			temp = temp.next;
		}
	}
}

//定义一个HeroNode，每个HerNode对象，都是一个节点
class HerNode {
	public int no; // 英雄编号
	public String name; // 英雄名称
	public String nickName; // 昵称
	public HerNode next; // 指向下一个节点

	public HerNode() {

	}

	public HerNode(int hNo, String hName, String nickName) {
		this.no = hNo;
		this.name = hName;
		this.nickName = nickName;
	}

	@Override
	public String toString() {
		return "HerNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
	}
}